跳至主要内容

LeetCode 242. Valid Anagram (Easy)

題目連結​

https://leetcode.com/problems/valid-anagram/

解題思路​

  • 先了解 Anagram 的意思

解法 1: Hash Map​

function isAnagram(s: string, t: string): boolean {
    if (s.length !== t.length) {
        return false;
    }

    const charCount = new Map<string, number>();

    for (const char of s) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }

    for (const char of t) {
        if (!charCount.has(char)) {
            return false;
        }

        charCount.set(char, charCount.get(char) - 1);

        if (charCount.get(char) < 0) {
            return false;
        }
    }

    return true;
};

Complexity :​

  • Time: O(n)，n 是字串 s 的長度
  • Space: O(k)，k 代表 charCount 儲存的字母數量大小

解釋:​

  1. 先判斷字串長度是否相同，如過不相等返回 false
  2. 建立一個名為 charCount 的 Map，第一個值存字母，第二個值存字母的數量
  3. 用 for...of 將 s 的值和數量放到 Map 中
  4. 用 for...of 將 t 的值來和 Map 比較，
  • 如果 t 中出現了 s 中没有的字母，返回 false
  • 接著將 charCount 裡相對應的數量減一
  • 如果字母的出現次數小於 0，說明 t 中某個字母出現的次數比 s 多，並不是 Anagram
  1. 如果以上檢查都正確返回 true

解法 2: Sorting​

function isAnagram(s: string, t: string): boolean {
  return s.split("").sort().join("") === t.split("").sort().join("");
}

Complexity :​

  • Time: O(nlogn)，n 是輸入的字串 s 和 t 的長度，split、sort 和 join 這些操作時間複雜度都是 O(nlogn)

  • Space: O(n)，因為函數中創建了兩個長度為 n 的陣列來存儲 s 和 t 的字符

解釋:​

如果兩個字串是 Anagram ，代表內容都相同只是順序不同。所以可以透過排序的方式判斷兩個字串是否相同。

  1. 先用 split 將字串換成陣列
  2. 接著用 sort 將陣列排序，如果 sort 沒傳入任何參數，排序的方式會根據字串的 Unicode 編碼進行排序
  3. 最後用 join 將陣列重新變回字串

這題還有很多種解題方式，大家可以嘗試看看